package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.DaiBi;
import cn.pugle.oj.catalog.DynamicProblem;

/**
 * Created by tzp on 15-10-20.
 * 最长回文子串 v2
 * 其中一些减少执行路径的小tips有很多，但是不能实际缩减这种方法的时间复杂度， n3方？
 * Time Limit Exceeded
 */
public class LC5_LongestPalindromicSubstringV2 implements DaiBi, DynamicProblem {
    public String longestPalindrome(String s) {
        int longest = 0, longestX = 0, longestY = 0;
        for (int i = 0; i < s.length() - 1; i++) {
            for (int j = s.length() - 1; j > i && j - i + 1 > longest; j--) {
                boolean isPalindromic = true;
                int begin = i, end = j;
                while (begin < end) {
                    if (s.charAt(begin) != s.charAt(end)) {
                        isPalindromic = false;
                        break;
                    }
                    begin++;
                    end--;
                }
                if (isPalindromic) {
                    longest = j - i + 1;
                    longestX = i;
                    longestY = j;
                    break;
                }
            }
            if (longest == s.length() - i) {
                break;
            }
        }
        if (longest > 1) {
            return s.substring(longestX, longestY + 1);
        } else {
            return s;
        }
    }

    /**
     * 即使是final的方法也不如‘内联’的快？
     */
    public final boolean isPalindromic(String str, int begin, int end) {
        while (begin < end) {
            if (str.charAt(begin) != str.charAt(end)) {
                return false;
            }
            begin++;
            end--;
        }
        return true;
    }

    public static void main(String[] args) {
        long beginTime = System.currentTimeMillis();
        System.out.println(new LC5_LongestPalindromicSubstringV2().longestPalindrome("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabcaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"));
        System.out.println(System.currentTimeMillis() - beginTime);
    }
}
